The first collection of Leibniz's key writings on the binary system, newly translated, with many previously unpublished in any language. -/- The polymath Gottfried Wilhelm Leibniz (1646–1716) is known for his independent invention of the calculus in 1675. Another major—although less studied—mathematical contribution by Leibniz is his invention of binary arithmetic, the representational basis for today's digital computing. This book offers the first collection of Leibniz's most important writings on the binary system, all newly translated by the authors with many (...) previously unpublished in any language. Taken together, these thirty-two texts tell the story of binary as Leibniz conceived it, from his first youthful writings on the subject to the mature development and publication of the binary system. -/- As befits a scholarly edition, Strickland and Lewis have not only returned to Leibniz's original manuscripts in preparing their translations, but also provided full critical apparatus. In addition to extensive annotations, each text is accompanied by a detailed introductory “headnote” that explains the context and content. Additional mathematical commentaries offer readers deep dives into Leibniz's mathematical thinking. The texts are prefaced by a lengthy and detailed introductory essay, in which Strickland and Lewis trace Leibniz's development of binary, place it in its historical context, and chart its posthumous influence, most notably on shaping our own computer age. (shrink)

By theword problemfor some class of algebraic structures we mean the problem of determining, given a finite setEof equations between words and an additional equationx=y, whetherx=ymust hold in all structures satisfying each member ofE. In 1947 Post [P] showed the word problem for semigroups to be undecidable. This result was strengthened in 1950 by Turing, who showed the word problem to be undecidable forcancellation semigroups,i.e. semigroups satisfying thecancellation propertyNovikov [N] eventually showed the word problem for groups to be undecidable.In 1966 (...) Gurevich [G] showed the word problem to be undecidable forfinitesemigroups. However, this result on finite structures has not been extended to cancellation semigroups or groups; indeed it is easy to see that a finite cancellation semigroup is a group, so both questions are the same. We do not here settle the word problem for finite groups, but we do show that the word problem is undecidable for finite semigroups with zero satisfying an approximation to the cancellation property. (shrink)

A Krom formula of pure quantification theory is a formula in conjunctive normal form such that each conjunct is a disjunction of at most two atomic formulas or negations of atomic formulas. Every class of Krom formulas that is determined by the form of their quantifier prefixes and which is known to have an unsolvable decision problem for satisfiability is here shown to be a conservative reduction class. Therefore both the general satisfiability problem, and the problem of satisfiability in finite (...) models, can be effectively reduced from arbitrary formulas to Krom formulas of these several prefix types. (shrink)

Offering an introduction to algorithms, this work considers automata in the context of their applications, NP-completeness, Turing machine notation and Chomsky normal form.